Adjacency List: An Efficient Graph Storage Method, What Makes It Better Than Adjacency Matrix?

This article introduces the basic concepts of graphs and two core storage methods: the adjacency matrix and the adjacency list. A graph consists of vertices (e.g., social network users) and edges (e.g., friendship relationships). The adjacency matrix is a 2D array where 0/1 indicates whether there is an edge between vertices. It requires O(n²) space with n being the number of vertices, and checking an edge takes O(1) time. However, it wastes significant space for sparse graphs (few edges). The adjacency list maintains a neighbor list for each vertex (e.g., a user’s friend list), with space complexity O(n + e) where e is the number of edges, as it only stores actual edges. Checking an edge requires traversing the neighbor list (O(degree(i)) time, with degree(i) being the number of neighbors of vertex i), but traversing neighbors is more efficient in practice. A comparison shows that the adjacency list significantly outperforms the adjacency matrix in both space and time efficiency for sparse graphs (most practical scenarios). It is the mainstream storage method for graph problems (e.g., shortest path algorithms), offering better space saving and faster traversal.